package com.jxb.test20241216;

import com.jxb.tree.TreeNode;

public class Sort9 {

    public static void main(String[] args) {

    }

    //数组长度
    static int len;

    public static int[] sortArr(int[] nums) {
        if (nums.length <= 0) {
            return nums;
        }
        len = nums.length;
        //构建成一个最大堆
        buildMaxHeap(nums);
        //将堆首元素和末尾元素进行交换
        while (len > 0) {
            swap(nums,0,len-1);
            len--;
            adjustHeap(nums,0);
        }
        return nums;
    }

    private static void buildMaxHeap(int[] nums) {
        for (int i = (len/2 -1);i>=0;i--) {
            adjustHeap(nums, i);
        }
    }

    private static void adjustHeap(int[] nums, int i) {
        int maxIndex = i;
        int left = 2*i + 1;
        int right = 2*(i+1);
        if (right < len && nums[right] > nums[maxIndex] && nums[right] > nums[left]) {
            maxIndex = right;
        }
        if (left < len && nums[left] > nums[maxIndex]) {
            maxIndex = left;
        }
        //经过2次判断后，判断父节点是否是最大值，不是最大值进行交换
        if (i != maxIndex) {
            swap(nums,maxIndex,i);
            adjustHeap(nums,maxIndex);//?????
        }
    }

    private static void swap(int[] nums, int maxIndex, int i) {
        int temp = nums[maxIndex];
        nums[maxIndex] = nums[i];
        nums[i] = temp;
    }

}
